﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;
using DataStructuresCSharp.Node;

namespace DataStructuresCSharp.KeyValueCollection
{
    public abstract class BaseBinarySearchTree<TKey, TValue, TNode> : IKeyValueCollection<TKey, TValue> where TNode : BaseBinaryTreeNode<KeyValuePair<TKey, TValue>, TNode>
    {
        protected virtual TNode Root { get; set; }
        protected int _count;
        protected int _version;
        protected readonly IComparer<TKey> _comparer;
        protected readonly EqualityComparer<TValue> _valueComparer;

        protected BaseBinarySearchTree(IComparer<TKey> comparer = null)
        {
            _count = 0;
            _version = 0;
            _comparer = comparer ?? Comparer<TKey>.Default;
            _valueComparer = EqualityComparer<TValue>.Default;
        }

        protected BaseBinarySearchTree(IDictionary<TKey, TValue> dictionary, IComparer<TKey> comparer = null) : this(comparer)
        {
            if (dictionary == null) throw new ArgumentNullException(nameof(dictionary));
            foreach (var item in dictionary)
            {
                Add(item);
            }
        }

        public virtual bool ContainsValue(TValue value)
        {
            return Traverse().Any(node => _valueComparer.Equals(node.Item.Value, value));
        }

        public virtual IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            return new BaseEnumerator(this);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public void Add(KeyValuePair<TKey, TValue> item)
        {
            Add(item.Key, item.Value);
        }

        protected static void Clear(TNode root)
        {
            if (root == null) return;
            var queue = new Queue<TNode>();
            queue.Enqueue(root);
            while (queue.Count != 0)
            {
                var item = queue.Dequeue();
                if (item.HasLeftChild) queue.Enqueue(item.LeftChild);
                if (item.HasRightChild) queue.Enqueue(item.RightChild);
                item.Invalidate();
            }
        }

        public virtual void Clear()
        {
            Clear(Root);
            Root = null;
            _count = 0;
            _version++;
        }

        public virtual bool Contains(KeyValuePair<TKey, TValue> item)
        {
            return BinarySearch(item.Key, true, item.Value) != null;
        }

        public virtual void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            if (array == null) throw new ArgumentNullException(nameof(array));
            if ((uint)arrayIndex > (uint)array.Length) throw new ArgumentOutOfRangeException(nameof(arrayIndex));
            if (array.Length < _count + arrayIndex) throw new ArgumentException(nameof(array));

            foreach (var node in Traverse())
            {
                array[arrayIndex++] = node.Item;
            }
        }

        public int Count => _count;

        public bool IsReadOnly => false;

        public abstract void Add(TKey key, TValue value);

        public abstract bool Remove(TKey key);

        public abstract bool Remove(KeyValuePair<TKey, TValue> item);

        public virtual bool ContainsKey(TKey key)
        {
            return BinarySearch(key) != null;
        }

        public virtual bool TryGetValue(TKey key, out TValue value)
        {
            var node = BinarySearch(key);
            if (node == null)
            {
                value = default(TValue);
                return false;
            }
            value = node.Item.Value;
            return true;
        }

        public virtual TValue this[TKey key]
        {
            get
            {
                var node = BinarySearch(key);
                if (node == null) throw new KeyNotFoundException();
                return node.Item.Value;
            }

            set
            {
                var node = BinarySearch(key);
                if (node == null) Add(key, value);
                else node.Item = new KeyValuePair<TKey, TValue>(key, value);
                _version++;
            }
        }

        public abstract ICollection<TKey> Keys { get; }

        public abstract ICollection<TValue> Values { get; }

        protected IEnumerable<TNode> InOrderTraverseNonRecursive()
        {
            /*
            根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，
            然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，
            然后按相同的规则访问其右子树。因此其处理过程如下：
               对于任一结点P，
              1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
              2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
              3)直到P为NULL并且栈为空则遍历结束
            */
            var s = new Stack<TNode>();
            var p = Root;
            while (p != null || s.Count != 0)
            {
                while (p != null)
                {
                    s.Push(p);
                    p = p.LeftChild;
                }
                if (s.Count != 0)
                {
                    var top = s.Pop();
                    yield return top;
                    p = top.RightChild;
                }
            }
        }

        protected virtual IEnumerable<TNode> Traverse()
        {
            return InOrderTraverseNonRecursive();
        }

        protected TNode BinarySearch(TKey key, bool checkValue = false, TValue value = default(TValue))
        {
            if (key == null) throw new ArgumentNullException(nameof(key));
            var node = Root;
            while (node != null)
            {
                var cmp = _comparer.Compare(node.Item.Key, key);
                if (cmp == 0) return (checkValue && !_valueComparer.Equals(node.Item.Value, value)) ? null : node;
                var childIndex = cmp > 0 ? 0 : 1;
                node = node.Children[childIndex];
            }
            return null;
        }

        private struct BaseEnumerator : IEnumerator<KeyValuePair<TKey, TValue>>
        {
            private IEnumerator<TNode> _enumerator;
            private readonly BaseBinarySearchTree<TKey, TValue, TNode> _tree;
            private readonly int _version;
            private int _index;

            internal BaseEnumerator(BaseBinarySearchTree<TKey, TValue, TNode> tree)
            {
                _tree = tree;
                _enumerator = tree.Traverse().GetEnumerator();
                _version = tree._version;
                _index = -1;
            }

            public void Dispose()
            {
                _enumerator.Dispose();
            }

            public bool MoveNext()
            {
                if (_version != _tree._version) throw new InvalidOperationException();
                if (!_enumerator.MoveNext())
                {
                    _index = _tree.Count;
                    return false;
                }
                ++_index;
                return true;
            }

            public void Reset()
            {
                if (_version != _tree._version) throw new InvalidOperationException();
                _enumerator = _tree.Traverse().GetEnumerator();
                _index = -1;
            }

            public KeyValuePair<TKey, TValue> Current
            {
                get
                {
                    if (_index < 0 || (_index >= _tree.Count)) throw new InvalidOperationException();
                    return _enumerator.Current.Item;
                }
            }
            object IEnumerator.Current => Current;
        }
    }
}
